/* 2616. 最小化数对的最大差值 */
/* https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/570819965/ */
/* 时间：10/9 难度：中等*/
/* 二分搜索 */

代码：
class Solution
{
public:
    int minimizeMax(vector<int> &nums, int p)
    {
        // 假设差值的最大值最小为x；（看看是否能找到p对，如果能找的则说明太大，就要往小的值缩一缩，找不到说明x太严格了，再往大松一松）
        // 思路：将数组排序从小到大排序，假设为a，b，c，d，如果（a，b）配对<x，则就让（a，b）配对，因为数组是从小到大排列好的，所以不需要有如果（a，b）配对了，但是（c，d）也满足<x的顾虑。看一共能组成多少对，如果》=p对,说明x太大了，需要往下松一松，反之亦然。

        sort(nums.begin(), nums.end());
        int left = 0, right = INT_MAX; // 宏定义为int类型的最大值
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (isok(nums, p, mid)) // isok就是check函数
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left;
    }

    bool isok(vector<int> &nums, int p, int x) // 检查能否找出p对，在给定差值x的情况下
    {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (i + 1 < n && nums[i + 1] - nums[i] <= x)
            {
                count++;
                i = i + 1;
            }
        }
        return count >= p;
    }
};